Computer software comprises a set of instructions to be executed by a data processing system. Generally, it is the computer software which makes a data processing system useful, by providing the instructions for the data processing system to carry out productive tasks. Computer software provides instructions that enable a data processing system to function as, for example, a word processing device, spreadsheet device, or an Internet browsing device.
There are a wide variety of different data processing systems capable of using computer software. Accordingly, as used herein, the term “data processing system” is intended to have a broad meaning, and may include personal computers, laptop computers, palmtop computers, handheld computers, network computers, servers, mainframes, workstations, cellular telephones and similar wireless devices, personal digital assistants and other electronic devices on which computer software may be installed. The terms “computer”, “computer software”, “computer program”, “computer programming”, “software”, “software program” and related terms are intended to have a similarly broad meaning.
Generally, modern computer software is originally written in a “high level” computer programming language using syntactic constructs that are comprehensible by a programmer to represent the instructions embodied in the software. For example, in the “C” programming language, the syntactic term “printf” is used to represent an instruction to the data processing system to print the contents of a particular data field. High level computer programming languages are useful because their syntactic constructs make it easier for programmers to create computer software, since they do not need to compose instructions in a language that would be directly understood by the data processing system. Writing instructions in such a language would be far more difficult because such languages bear little or no resemblance to any human language.
Instructions written in a high level computer programming language, however, generally cannot be directly understood and implemented by a data processing system. Therefore, before a computer program written in a high level computer programming language may be used by a data processing system, it must first be “compiled” into language that will be understood by the target data processing system. Compiling is a process, usually carried out by a computer program called a “compiler”, in which the syntactic constructs of the high level computer programming language are in essence translated into instructions in a language that will be understood by the target data processing system (possibly through an intermediate software layer). The result of the “compiling” or “compilation” process is known as “executable code”, meaning computer program code that can be executed by the data processing system either directly or by an intermediate software layer.
High level computer programming languages may be viewed as falling within one of two broad types: statically compiled languages, and dynamically compiled languages.
In statically compiled languages, the compilation process is carried out a single time before any code is executed, and the result of the compilation is executable code that can be implemented directly by the data processing system without any intermediate software layer. Statically compiled languages include C, C++, FORTRAN, PL/I, COBOL and Ada.
In dynamically compiled languages, such as Java™, the source code is first compiled into an intermediate form that can be implemented by an intermediate software layer, such as a Java virtual machine (JVM). In Java, this intermediate form is known as “bytecode”. (Java and all Java-based trademarks are trademarks of Sun Microsystems, Inc. in the United States, other countries, or both). Typically, but not necessarily, the intermediate software layer will carry out additional compilation each time the computer program is run, usually to translate the intermediate form of the source code into executable code that can be directly executed by the data processing system.
Usually, a direct translation of a computer program written in a high level computer programming language into executable code will not result in particularly efficient executable code. There may be for example, redundant operations, inefficient allocations of memory within the data processing system, and other circumstances which would impair the efficiency of the executable code. In addition, the order of instructions specified by the human programmer may not be the most efficient, or even nearly the most efficient, way to carry out the instructions on the data processing system. To obviate these difficulties, various performance improvement algorithms are applied when compiling computer programs written in a high level computer programming language. However, this approach entails a number of difficulties.
With statically compiled languages, the main problem is that at the time the computer program is compiled, the compiler program does not possess any of the information that can only be gathered at runtime (that is, when the computer program is executed), and which information can have a substantial impact on the efficiency of the computer program. An additional problem is that the compiler program may not be aware of the particular data processing system on which the resulting executable code will be executed, and will therefore be unable to adapt the executable code to the hardware features of the data processing system on which it will run. A number of different approaches may be applied to these problems.
The first approach is to simply ignore the problems, and statically compile the computer program for as specific or as general an architecture as the user specifies. In this case, statically compiled versions and dynamic or runtime checks are the only way to exploit some predefined runtime behavior or new or non-ubiquitous hardware features.
The second approach is to have a “training run” in which the user compiles the target program code once in a mode where the code, when executed, gathers useful information. This code is then executed using “training data” that is assumed to be typical of what will be supplied during application deployment. This is followed by a second compilation which exploits the knowledge gathered in the training run. There are a number of problems with this approach. First, it may be tedious and quite difficult to compose a set of training data that is meaningful and that covers all real execution scenarios. Second, and more importantly, experience has shown that very few software vendors are willing to embrace such mechanisms. Third, there are optimizations that are not amenable to collecting profiling information using an instrumented form of executable code, because the real behavior of the application is perturbed by the instrumentation. Fourth, there is a class of optimizations (e.g. invocation invariants) which are not correctly addressed with this mechanism and, in fact, one of the complexities of generating meaningful training data is having enough variation in the input to keep the system from falsely identifying opportunities for specialization that are only an artifact of the training data and not representative of the actual application in production.
A third approach is to compile some or all of the application “on demand.” That is, a compiler would defer compilation of portions of or all of the application until the particular portion is executed, and then compile the portions based on available information about the runtime environment. However, this means that execution of the application will be interrupted by compilation, causing the application to run more slowly than is desirable, especially in the early stages of execution.
A fourth method involves (statically) compiling source code written in a statically compiled language so that the resulting executable code contains optimization directives. When the code is executed, the optimization directives may enable optimizations to be applied at runtime based on runtime data. See, for example, U.S. Pat. No. 6,427,234 to Chambers et al. Optimization directives should not be confused with ordinary runtime checks typically found in executable code compiled from source code written in a statically compiled language. Optimization directives generally respond to runtime data by generating, at runtime, new, specialized code that is more suited to the environment indicated by the runtime data. In contrast, ordinary runtime checks merely control execution flow by checking runtime conditions and directing program execution along a selected one of a plurality of pre-existing paths (code for each pre-existing path having been generated at compile time).
The first and second approaches are often inapplicable to dynamically compiled languages, since the program (or at least most of the program) may not exist until runtime. The third method, when applied to a dynamically compiled language, results in (temporarily) reduced performance because of time spent on compilation.
In addition, with dynamically compiled languages, the compilation process will proceed once through a series of optimization steps to generate the final executable application. Therefore, if the environment in which the application is executing changes, the executable application may suffer from reduced performance because the circumstances that formed the basis on which the application was optimized no longer exist.